package Stack;
import java.util.*;
public class Exercise {

    public static void main(String[] args) {
        //首先学会将中缀表达式转换为后缀表达式
        //如:"1+((2+3)*4)-5"  转化->((1+((2+3)*4))-5)->将所有运算符移到对应括号的外面:((1((23)+4)*)+5)- 最后将所有括号去掉:123+4*+5-
//        逆波兰表达式：
//        逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
//        平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
//        该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
//        逆波兰表达式主要有以下两个优点
//        去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果
//        适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
        int val=evalRPN(new String[]{"10","6","9","3","+","-11","*","/","*","17","+","5","+"});
        System.out.println(val);
        boolean flg=isValid("[[[]]");
        System.out.println(flg);
        //总体思路就是:先入栈，如果栈的最后一个元素是popped里面的第一个元素，那么就说明栈中此时需要出栈，如果栈里面没有popped，那么就入栈
        //当i走完时判断栈是否为空，空就是满足，非空就说明没有这个出栈顺序
        boolean flg1=validateStackSequences(new int[]{1,2,3,4,5},new int[]{4,5,3,2,1});
        System.out.println(flg1);
    }
    public static int evalRPN(String[] tokens) {
        java.util.Stack<Integer> s1=new java.util.Stack<>();
        for(int i=0;i<tokens.length;i++) {
            if(!isOperation(tokens[i])) {
                s1.push(Integer.parseInt(tokens[i]));    //是数字就入栈。是运算符就运算，先入栈的数字是运算是左边的数字（观察得）
            }else {
                int num2=s1.pop();       //栈顶首个元素是运算符后面的数字
                int num1=s1.pop();
                int num=0;
                if(tokens[i].equals("+")) {
                    num=num1+num2;
                }else if(tokens[i].equals("-")) {
                    num=num1-num2;
                }else if(tokens[i].equals("*")) {
                    num=num1*num2;
                }else if(tokens[i].equals("/")){
                    num=num1/num2;
                }
                s1.push(num);           //运算完之后在吧结果入栈，能够进行下一次的运算
            }
        }
        return s1.pop();               //最后剩下的数字就是结果
    }
    private static boolean isOperation(String tokens) {
        if(tokens.equals("+")||tokens.equals("-")||tokens.equals("*")||tokens.equals("/")) {
            return true;
        }
        return false;
    }

    //本题所有特殊情况:1.)() 2.()) 3.(() 4.([)]
    public static boolean isValid(String s) {
        java.util.Stack<Character> s1=new java.util.Stack<>();
        for(int i=0;i<s.length();i++) {
            char ch=s.charAt(i);
            if(ch=='('||ch=='['||ch=='{') {              //如果是左括号就入栈
                s1.push(ch);
            }else {                                      //如果是有括号就进行匹配(因为是入一个就匹配，所以是一一对应的关系)
                if(s1.empty()) {                         //如果刚开始栈是空的也就代表着字符串的第一个字符是右括号，此时不可能匹配
                    return false;                        //如果左括号已经匹配完了，但是字符串中依然存在右括号，那么也不匹配
                }
                char ch2=s1.peek();
                if(ch2=='('&&ch==')'||ch2=='['&&ch==']'||ch2=='{'&&ch=='}') {
                    s1.pop();
                }else {                                  //([)]这种情况就是不匹配的，随着字符串往后走，遇到右括号和左括号不匹配
                    return false;
                }
            }
        }
        if(!s1.empty()) {                                //如果字符串走完，左括号还没匹配完说明左括号多
            return false;
        }
        return true;
    }

    public static boolean validateStackSequences(int[] pushed, int[] popped) {
        java.util.Stack<Integer> s1 = new java.util.Stack<>();
        int i=0;
        int j=0;
        for(;i<pushed.length;i++) {
            s1.push(pushed[i]);
            while(j<popped.length&&!s1.empty()&&s1.peek().equals(popped[j])) {           //j走完之后就结束，否则出现空指针异常
                s1.pop();
                j++;
            }
        }
        return s1.empty();                                      //如果栈为空就说明是弹出序列
    }
}
